Final Examination: Data Structures and Algorithms

Note: This final exam is developed based exclusively on the materials covered in the class so far, following the topics from Week 6 through Week 14. ***

Part 1: Multiple Choice Questions (20 Questions)

Instructions: Select the best answer. The correct answer is indicated in bold below each question.

Consider the pseudocode for evaluating a postfix expression. If the program attempts to execute the line operand1 = stack.pop() when the stack is empty, what type of error is guaranteed to be detected and reported by the model?
- A. Division by zero
- B. Too many operands
- C. Unrecognizable token
- D. Too few operands
  Correct Answer: D. Too few operands
A graph is considered ‘dense’ when:
- A. It is connected.
- B. It is acyclic.
- C. It has far fewer edges than possible.
- D. It has nearly the maximum possible number of edges.
  Correct Answer: D. It has nearly the maximum possible number of edges.
What is the time complexity required to iterate across all neighbors of all vertices in a sparse graph using an Adjacency List, where N is vertices and M is edges?
- A. O(N²)
- B. O(M)
- C. O(M/N)
- D. O(N)
  Correct Answer: D. O(N)
  For a sparse graph, M is typically close to N, so O(max(M, N)) simplifies to O(N)
When implementing a Linked Queue, which pointer must be updated during the add operation, regardless of whether the queue was empty or not?
- A. self.front
- B. self.size
- C. oldItem
- D. self.rear
  Correct Answer: D. self.rear
Which algorithm solves the all-pairs shortest path problem with a running time complexity of O(N³)?
- A. Dijkstra’s Algorithm
- B. Prim’s Algorithm
- C. Kruskal’s Algorithm
- D. Floyd’s Algorithm
  Correct Answer: D. Floyd’s Algorithm
If a Binary Search Tree (BST) becomes completely vine-like (highly unbalanced), the worst-case time complexity for the find operation degrades from logarithmic time to what?
- A. O(1)
- B. O(N) (Linear)
- C. O(N²)
- D. O(NlogN)
  Correct Answer: B. O(N) (Linear)
In the context of graph implementation, which data structure supports finding all adjacent vertices to a given vertex most efficiently for a very sparse graph?
- A. Adjacency List
- B. Adjacency Matrix
- C. Hash Table of all Edges
- D. A 2D array of distances
  Correct Answer: A. Adjacency List
If a graph traversal uses a stack (explicit or via recursion), what type of path exploration behavior does this process enforce?
- A. Visiting all neighbors at the current depth first.
- B. Going deeply into the graph before backtracking.
- C. Always choosing the shortest path.
- D. Following only simple paths.
  Correct Answer: B. Going deeply into the graph before backtracking.
During the recursive execution of a subroutine, the PVM pushes an ‘activation record’ onto the call stack. What critical piece of information does this record contain to allow the PVM to return to the calling routine?
- A. The object heap pointer
- B. The Return Address (locationCounter’s current value)
- C. The size of the program bytecode
- D. The current size of the stack
  Correct Answer: B. The Return Address (locationCounter’s current value)
What is the complexity of Kruskal’s or Prim’s algorithms for finding a Minimum Spanning Tree (MST), where E is the number of edges and V is the number of vertices?
- A. O(V²)
- B. O(ElogV)
- C. O(V+E)
- D. O(E³)
  Correct Answer: B. O(ElogV)
Which method in the LinkedVertex class is used to return an iterator over the vertices directly connected to it?
- A. getEdgeTo(toVertex)
- B. incidentEdges()
- C. neighboringVertices()
- D. getLabel()
  Correct Answer: C. neighboringVertices()
When an array is used to implement a binary tree, for a node at index i, what is the index of its parent?
- A. 2*i+1
- B. 2*i+2
- C. i−1
- D. (i−1)//2
  Correct Answer: D. (i−1)//2
In a LinkedPriorityQueue using a sorted linked list implementation, the pop method (removal from the front) inherits its complexity from the LinkedQueue class. Assuming front and rear pointers are maintained, what is the time complexity of pop?
- A. O(N)
- B. O(1)
- C. O(logN)
- D. O(N²)
  Correct Answer: B. O(1)
According to the EBNF grammar rules provided, which metasymbol indicates that a part of the expression is optional?
- A. {…}
- B. ∣
- C. (…)
- D. […]
  Correct Answer: D. […]
If a graph is being used to model one-way streets, which graph terminology best describes the edges used in this model?
- A. Unweighted edges
- B. Undirected edges
- C. Directed edges
- D. Incident edges
  Correct Answer: C. Directed edges
Which of the following operations is NOT provided by the LinkedDirectedGraph class but IS provided by the LinkedVertex class?
- A. addEdge(fromLabel, toLabel, weight)
- B. clearMark()
- C. sizeVertices()
- D. containsEdge(fromLabel, toLabel)
  Correct Answer: B. clearMark()
  Marking/unmarking is a vertex property
What specialized role does the Scanner class play in the overall architecture for evaluating expressions?
- A. It handles all user input/output.
- B. It performs the mathematical calculation.
- C. It maintains the operand stack.
- D. It performs lexical analysis, extracting tokens from the input string.
  Correct Answer: D. It performs lexical analysis, extracting tokens from the input string.
What is the maximum number of nodes possible in a full binary tree of height h=3?
- A. 4
- B. 7
- C. 8
- D. 15
  Correct Answer: D. 15
  2^(3+1) − 1 = 15
Which graph traversal is specifically used to order vertices in a DAG such that for every directed edge u→v, u comes before v?
- A. Depth-First Traversal
- B. Breadth-First Traversal
- C. Topological Sort
- D. Minimum Spanning Tree
  Correct Answer: C. Topological Sort
When inserting an item into a min-heap using the array implementation, the algorithm restores the heap property by moving the newly inserted item up toward the root. This process continues until the parent item is found to be:
- A. Equal to the item
- B. Greater than the item
- C. Less than or equal to the item
  Correct Answer: C. Less than or equal to the item
  parentItem <= item causes the loop to break

Part 2: Short Answer Questions (1-2 Words) (10 Questions)

Write your answer in 1-2 words.

Convert the following Infix expressions into its corresponding Postfix forms. Provide the result as a sequence of tokens separated by single spaces.

A * (B + (C - D) / E) to its Postfix form.

Correct Answer: A B C D - E / + *

What is the resulting numerical value of the Postfix expression: 25 5 2 / 3 1 + * - 2 +?

Correct Answer: 19
What term is used to describe the index variable that points to the logical end of an array-based queue in an implementation where items are not shifted left upon removal?
Answer: Rear
What is the specialized binary tree structure where interior nodes represent operators and leaf nodes represent atomic operands?
Answer: Expression tree
What specific feature of a priority queue ensures that patients with condition rank 1 (Critical) are processed before those with rank 3 (Fair)?
Answer: Priority
In the context of BST definition, what is another word for the “key” used for ordering comparisons?
Answer: Value

In a directed graph, if there is a directed edge from vertex u to vertex v, what is u called in relation to v?
Answer: Predecessor (or Source)
What kind of graph is a connected, acyclic graph?
Answer: Tree
What class defines the comparison logic (__lt__, __eq__) for non-comparable items being added to a priority queue?
Answer: Comparable
When performing a level order traversal on a binary tree, what data structure is used to manage the nodes that need to be visited next?
Answer: Queue
What is the complexity of the computational step in Dijkstra’s algorithm?
Answer: O(N²)

Part 3: Applied Questions (5 Questions)

1. Scenario: Data Processing Pipeline

A large tech company is designing a complex data processing pipeline where tasks have dependencies (e.g., Task B cannot start until Task A is complete). Some tasks are computationally expensive. The graph structure is known to have millions of nodes (tasks) and a relatively low number of edges (dependencies, M). The goal is to determine a valid sequence in which to run the tasks.

Query:
a) What specific type of graph structure must this pipeline conform to, and what specialized traversal algorithm should be applied?
b) Discuss the crucial storage trade-off decision (Adjacency List vs. Matrix) that must be made, justifying the choice based on the structure of the pipeline.

Answer:
a) The pipeline must conform to a Directed Acyclic Graph (DAG), as cycles would imply a logical deadlock. The required algorithm is Topological Sort.
b) Since the graph is sparse (millions of nodes, few edges), an Adjacency List is preferred over an Adjacency Matrix. The matrix would require O(N²) storage, which is prohibitive, while the list requires O(N+M), making it much more memory efficient.

2. Scenario: Airline Route Mapping

An airline wants to find the cheapest route between its hub city (S) and all other available cities (V). The cost of flying between any two cities (edges) is always positive. The total number of cities (N) is 100.

Query: Which algorithm—Dijkstra’s or Floyd’s—is appropriate for this task, and what is the computational complexity of the chosen algorithm? Justify your choice based on the problem requirements and time complexity.

Answer:
Chosen Algorithm: Dijkstra’s Algorithm.
Complexity: O(N²).
Justification: The problem asks for the shortest path from a single source vertex (the hub city S) to all other vertices. Dijkstra’s Algorithm is designed specifically to solve the single-source shortest path problem in a weighted graph where edge weights are non-negative. Its complexity is O(N²). Floyd’s Algorithm (Floyd-Warshall) solves the all-pairs shortest path problem, which is overkill for this scenario and has a higher complexity of O(N³). Since the task only requires paths from one hub, Dijkstra’s is more computationally efficient (O(N²) vs O(N³)) while satisfying the requirements.

3. Scenario: Stack-based Maze Solver

A backtracking algorithm is used to solve a maze. The stack stores the coordinates of alternative paths to explore.

Query:
If the algorithm reaches a dead end (a location with no adjacent, unvisited spaces), explain the mechanism by which the stack facilitates “backtracking” to an unexplored alternative path.

Answer:
The stack holds coordinates of alternative paths. When a dead end is reached, the algorithm pops locations off the stack until it finds one with unvisited neighbors, thus “backtracking” to the last point of divergence.

4. Scenario: Heap Insertion Analysis

An engineer is evaluating the performance of the add method for a Min-Heap implementation (using an array).

Query:
Based on the provided add method pseudocode, determine the worst-case time complexity for inserting an item into a heap of size N. Describe the structural event that leads to this worst-case scenario.

Answer:
Worst-case time complexity is O(logN). The worst case occurs when the new item is smaller than all existing items, requiring it to “bubble up” from the leaf to the root, performing swaps at each level.

5. Scenario: Directed vs. Undirected Graph Conversion

A development team has modeled a road network using an Undirected Graph where each edge {u,v} represents a two-way road between city u and city v. A new requirement demands the ability to assign different weights (traffic times) to travel from u to v versus v to u.

Query:
Explain how the existing undirected graph must be conceptually converted to a Directed Graph (Diagraph) to meet this requirement. Specifically, how many directed edges are needed for every single undirected edge in the original model, and how does this impact the overall edge count (M) for the new representation?

Answer:
Each undirected edge {u,v} must be replaced by two directed edges: (u,v) and (v,u), each with its own weight. The total number of edges in the directed graph will be twice the original number of undirected edges (2M).